package tips.p_others;

import java.util.HashMap;

/**
 * 给你一个整数数组 arr 和一个整数 difference，
 * 请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
 * 子序列 是指在不改变其余元素顺序的情况下，
 * 通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
 * <p>示例 1：
 * 输入：arr = [1,2,3,4], difference = 1
 * 输出：4
 * 解释：最长的等差子序列是 [1,2,3,4]。
 * <p>示例 2：
 * 输入：arr = [1,3,5,7], difference = 1
 * 输出：1
 * 解释：最长的等差子序列是任意单个元素。
 * <p>示例 3：
 * 输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
 * 输出：4
 * 解释：最长的等差子序列是 [7,5,3,1]。
 * <p>提示：
 * 1 <= arr.length <= 10^5
 * -10^4 <= arr[i], difference <= 10^4
 *
 * @author hc
 */
public class Demo1218 {

    public int longestSubsequence(int[] arr, int difference) {
        int max = 1;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            Integer val = map.get(arr[i] - difference);
            if (val != null) {
                map.put(arr[i], val + 1);
                max = Math.max(max, val + 1);
            } else {
                map.put(arr[i], 1);
            }
        }
        return max;
    }
}
